package leetcode

import "sort"

// https://leetcode.cn/problems/rabbits-in-forest/description/

// numRabbits 计算至少需要多少只兔子才能满足给定的答案数组。
// answers 是一个数组，其中每个元素代表一只兔子，值表示它之后还有多少只相同种类的兔子。
// 返回值是至少需要的兔子数量。
func numRabbits(answers []int) int {
	// n 为答案数组的长度
	n := len(answers)

	// 对答案数组进行排序，以便相同答案的兔子相邻
	sort.Slice(answers, func(i, j int) bool {
		return answers[i] < answers[j]
	})

	// answer 记录当前处理的答案
	answer := answers[0]
	// sameAnswerNum 记录当前答案的兔子数量
	sameAnswerNum := 1
	// sameRabbitNum 记录具有相同答案的兔子群体应有的数量
	sameRabbitNum := answer + 1
	// ans 用于累计最少需要的兔子数量
	ans := 0

	// 遍历排序后的答案数组
	for i := 1; i < n; i++ {
		// newAnswer 记录新的答案
		newAnswer := answers[i]
		if newAnswer == answer {
			// 如果答案相同，增加同答案兔子的数量
			sameAnswerNum++
			continue
		}
		// 计算并累加同答案兔子群体的数量
		ans += IntCeil(sameAnswerNum, sameRabbitNum) * sameRabbitNum
		// 重置同答案兔子的数量和答案值
		sameAnswerNum = 1
		answer = newAnswer
		sameRabbitNum = answer + 1
	}

	// 处理最后一个答案对应的兔子群体
	ans += IntCeil(sameAnswerNum, sameRabbitNum) * sameRabbitNum

	// 返回最少需要的兔子数量
	return ans
}

// IntCeil 计算整数除法的向上取整结果。
//
// 为什么表达式 (x + y - 1) / y 可以实现 x/y 的向上取整。
// 当我们进行 x 除以 y 的操作时，我们希望将 x 分成若干个 y 的整数倍以及一个小于 y 的余数。那么在进行向上取整时，如果余数不为 0，我们需要将商加 1 以确保取到比原商更大的整数值。
// 考虑 x 除以 y 的结果 q 和余数 r，即 x = q * y + r，其中 0 <= r < y。
// 现在让我们来看看表达式 (x + y - 1) / y 是如何实现向上取整的：
// 1.当 r == 0 时，即余数为 0，表达式变为 (q * y + y - 1) / y = q + (y-1)/y，由于 (y-1)/y 恒小于 1，所以向上取整的结果还是 q。
// 2.当 r != 0 时，即余数不为 0，表达式变为 (q * y + r + y - 1) / y = q + (r+y-1)/y，此时 (r+y-1)/y 大于 0 且小于 1，所以向上取整的结果为 q + 1。
func IntCeil(x, y int) int {
	return (x + y - 1) / y
}
